제2장 핵심 데이터 구조와 알고리즘

1. 블록 해싱(Block Hashing)과 메모리 관리

현대 로봇 공학, 특히 자율 주행과 실시간 3D 환경 인식 분야에서 ’매핑(Mapping)’은 로봇이 자신의 위치를 파악하고 경로를 계획하기 위한 가장 근본적인 토대를 제공한다. NvBlox는 이러한 매핑 프로세스를 GPU 가속을 통해 혁신적으로 가속화한 라이브러리로, 그 성능의 핵심에는 GPU 아키텍처의 특성을 극한으로 활용하는 정교한 데이터 구조와 메모리 관리 기법이 자리 잡고 있다. 본 장에서는 NvBlox가 채택하고 있는 **희소 복셀 그리드(Sparse Voxel Grid)**의 구조적 원리와, 이를 GPU 상에서 효율적으로 운용하기 위한 블록 해싱(Block Hashing) 알고리즘, 그리고 대규모 3D 데이터를 실시간으로 처리하기 위한 메모리 최적화 전략에 대해 심층적으로 분석한다. 이는 단순한 자료구조의 선택을 넘어, 대규모 병렬 연산 장치인 GPU의 하드웨어적 제약과 강점을 소프트웨어 아키텍처에 어떻게 녹여냈는지를 보여주는 시스템 설계의 정수라 할 수 있다.

1.1 희소(Sparse) 복셀 그리드 구조의 이해

1.1.1 차원 공간 표현의 난제: 차원의 저주와 메모리 효율성

3차원 공간을 디지털 데이터로 표현하는 가장 직관적인 방법은 공간을 균일한 격자(Grid)로 나누고, 각 격자(Voxel, Volumetric Pixel)에 정보를 저장하는 것이다. 그러나 이 방식은 맵의 크기가 증가함에 따라 필요한 메모리 양이 세제곱( $O(N^3)$ )으로 급증하는 ‘차원의 저주(Curse of Dimensionality)’ 문제에 직면한다. 예를 들어, 가로, 세로, 높이가 각각 100m인 공간을 5cm 해상도의 복셀로 표현하려면, $2000 \times 2000 \times 2000 = 80$ 억 개의 복셀이 필요하며, 각 복셀이 4바이트의 정보만 담는다 해도 약 32GB의 메모리가 요구된다. 이는 일반적인 임베디드 로봇 시스템이나 엣지 디바이스에서는 감당하기 어려운 수준이다.1

더욱 중요한 사실은, 실제 물리적 환경에서 물체의 표면(Surface)이 차지하는 부피는 전체 공간의 극히 일부분(일반적으로 5% 미만)에 불과하다는 점이다. 로봇이 주행하는 공간의 대부분은 ’빈 공간(Free Space)’이거나 아직 탐색하지 않은 ’미지 영역(Unknown Space)’이다. 따라서 전체 공간에 대해 메모리를 할당하는 밀집 그리드(Dense Grid) 방식은 95% 이상의 메모리를 무의미한 정보(빈 공간)를 저장하는 데 낭비하게 된다.

이러한 비효율성을 해결하기 위해 로봇 공학계에서는 옥트리(Octree)와 같은 계층적 트리 구조를 오랫동안 사용해 왔다(예: OctoMap). 트리는 데이터가 존재하는 영역만 노드로 분할하여 저장하므로 메모리 효율이 우수하다. 그러나 트리 구조는 본질적으로 포인터를 따라가는 순차적 탐색(Pointer-chasing)을 필요로 하며, 이는 수천 개의 코어가 동시에 데이터를 처리해야 하는 GPU 아키텍처와는 상극이다. GPU는 메모리에 연속적으로 접근할 때(Coalesced Access) 최고의 성능을 발휘하는데, 트리 구조의 불규칙한 메모리 접근 패턴은 캐시 미스(Cache Miss)를 유발하고 스레드 간 실행 분기(Divergence)를 초래하여 병렬 처리 효율을 급격히 떨어뜨린다.1

1.1.2 NvBlox의 해법: 블록 기반의 희소성(Sparsity)

NvBlox는 밀집 그리드의 빠른 접근 속도( $O(1)$ )와 트리 구조의 메모리 효율성을 동시에 달성하기 위해 블록 해싱(Block Hashing) 기반의 희소 복셀 그리드 구조를 채택했다. 이 구조는 전체 3D 공간을 균일한 크기의 ’블록(Block)’으로 나누되, 실제 센서 데이터(LiDAR 포인트 클라우드 또는 Depth 이미지)가 관측된 표면 근처의 블록들만 메모리에 동적으로 할당한다.2

블록(Block)의 정의: NvBlox에서 ’블록’은 데이터 관리의 최소 단위이자, 메모리 할당의 기본 단위다. 각 블록은 내부적으로 작은 3차원 복셀 배열을 포함한다. 일반적으로 NvBlox는 8x8x8 크기의 복셀 집합을 하나의 블록으로 정의한다.5 즉, 하나의 블록은 512개의 복셀을 담고 있다.
전역 희소성, 국소 밀집성 (Globally Sparse, Locally Dense): 이 구조의 핵심 철학은 “전체적으로는 희소하게(Sparse), 국소적으로는 밀집하게(Dense)” 데이터를 관리하는 것이다.
전역적 희소성: 3D 공간 전체 좌표계에서 블록들은 띄엄띄엄 존재한다. 이는 해시 테이블을 통해 관리되며, 데이터가 없는 빈 공간에는 블록이 할당되지 않아 메모리를 절약한다.
국소적 밀집성: 일단 할당된 블록 내부(8x8x8 복셀)는 연속된 메모리 공간에 저장된 밀집 배열(Dense Array)이다. 이는 GPU가 블록 내부의 데이터를 처리할 때(예: 삼선형 보간(Trilinear Interpolation)이나 그래디언트 계산), 메모리 주소를 규칙적으로 예측할 수 있게 하여 캐시 적중률(Cache Hit Rate)을 극대화한다.6

1.1.3 왜 8x8x8인가? GPU 하드웨어와의 상관관계 분석

블록의 크기를 $8 \times 8 \times 8$ 로 설정한 것은 임의의 선택이 아니라, NVIDIA GPU 하드웨어 아키텍처에 대한 깊은 이해를 바탕으로 한 최적화의 결과다.

워프(Warp) 실행 모델과의 정렬: NVIDIA GPU는 32개의 스레드를 하나의 ’워프’로 묶어 동시에 실행한다(SIMT 구조). 블록 내부의 복셀 수가 512개( $8^3$ )이므로, 이는 32의 배수(16 워프)로 떨어져 스레드 블록을 구성하기에 매우 용이하다. 블록 하나를 처리하기 위해 하나의 스레드 블록(Thread Block)을 할당하거나, 워프 단위로 작업을 분배할 때 나머지가 발생하지 않아 연산 자원의 낭비를 최소화할 수 있다.8
캐시 라인(Cache Line) 및 메모리 트랜잭션: GPU의 L1/L2 캐시는 일반적으로 128바이트 크기의 캐시 라인 단위로 데이터를 가져온다. 8x8x8 블록 구조는 인접한 복셀들이 메모리 상에 인접하게 배치되도록 유도(Z-order Curve 또는 선형 인덱싱)하여, 한 번의 메모리 요청으로 필요한 주변 복셀 데이터들을 함께 가져오는 효과를 낸다. 만약 블록 크기가 너무 작다면(예: 4x4x4), 블록 자체를 관리하기 위한 메타데이터(해시 테이블 엔트리, 포인터 등)의 오버헤드 비율이 데이터 크기에 비해 상대적으로 커져 메모리 효율이 떨어진다.
표면 대 부피 비(Surface-to-Volume Ratio)의 균형: 블록 크기가 너무 크다면(예: 16x16x16), 표면을 스치기만 해도 4096개의 복셀을 메모리에 할당해야 한다. 이 중 실제 표면 정보(TSDF 값이 0에 가까운)를 담는 복셀은 소수이고 나머지는 Truncation distance 밖의 의미 없는 값들로 채워지게 되어, 희소 구조를 사용하는 이점(메모리 절약)이 희석되는 ’내부 단편화(Internal Fragmentation)’가 발생한다.9 $8 \times 8 \times 8$ 은 이러한 오버헤드와 단편화 사이의 균형점(Sweet Spot)으로, 로봇 매핑에서 요구하는 일반적인 해상도(Voxel Size 2cm~10cm)에서 최적의 성능을 보여준다.10

1.1.4 TSDF와 데이터 페이로드(Payload)

각 복셀은 단순한 점유 여부(0 또는 1) 이상의 풍부한 정보를 담고 있다. NvBlox는 표면 재구성의 정밀도를 높이기 위해 TSDF (Truncated Signed Distance Field) 방식을 사용한다.

거리 값(Distance): 표면까지의 최단 거리를 부호 있는 실수(float)로 저장한다. 표면 앞쪽은 양수, 뒤쪽은 음수이며, 표면( $d=0$ )을 정밀하게 보간하여 추출할 수 있다.
가중치(Weight): 해당 복셀의 거리 값이 얼마나 신뢰할 수 있는지, 혹은 얼마나 많은 센서 관측값으로부터 통합되었는지를 나타내는 누적 가중치다.
색상(Color): 시각화를 위한 RGB 정보.

이러한 데이터들은 각 블록 내에 구조화되어 저장되며, NvBlox는 이를 통해 단순한 장애물 회피를 넘어선 고해상도 3D 컬러 메쉬(Mesh) 생성까지 실시간으로 수행한다.2

1.2 GPU 친화적 데이터 구조 - 해시 테이블과 메모리 접근 최적화

희소하게 분포된 블록들을 효율적으로 관리하기 위해서는, 3차원 공간 좌표 $(x, y, z)$ 를 입력받아 해당 블록이 저장된 실제 메모리 주소를 즉각적으로 반환해주는 인덱싱 시스템이 필요하다. CPU 기반 시스템에서는 std::unordered_map과 같은 동적 해시 맵을 사용하지만, GPU 환경에서 이를 구현하는 것은 차원이 다른 난이도의 과제다. 수천 개의 스레드가 동시에 맵을 조회(Read)하고 갱신(Write)해야 하며, 커널 실행 중에는 동적 메모리 할당(malloc)이 사실상 불가능하거나 매우 느리기 때문이다. NvBlox는 이러한 제약을 극복하기 위해 개방형 주소 지정(Open Addressing) 기반의 GPU 해시 테이블과 정적 메모리 풀(Static Memory Pool) 전략을 사용한다.1

1.2.1 공간 해싱 함수(Spatial Hash Function)와 인덱싱

NvBlox는 3차원 블록 인덱스를 1차원 해시 테이블 인덱스로 변환하기 위해 공간 해싱 함수를 사용한다. 이는 Niessner 등의 연구에서 제안된 XOR 기반 해시 함수를 따르며, 큰 소수(Large Prime Numbers)를 활용하여 비트를 섞음으로써 공간적 인접성이 해시 충돌로 이어지는 것을 방지한다.5
$H(x, y, z) = ( (x \cdot p_1) \oplus (y \cdot p_2) \oplus (z \cdot p_3) ) \mod n$
여기서 $p_1 = 73856093$ , $p_2 = 19349669$ , $p_3 = 83492791$ 과 같은 매우 큰 소수가 사용되며, $n$ 은 해시 테이블(버킷 배열)의 크기다. 이 연산은 GPU의 정수 연산 유닛(ALU)에서 매우 빠르게 처리되며, 비트 연산(XOR)을 사용하므로 분기 예측 실패나 메모리 지연 없이 수행된다.

1.2.2 GPU 해시 테이블 구현: `stdgpu`와 개방형 주소 지정

NvBlox의 해시 테이블은 독일 카를스루에 공과대학(KIT) 등에서 개발된 stdgpu 라이브러리의 구현 철학을 공유하거나 이를 내장하여 사용한다.1

개방형 주소 지정(Open Addressing)의 필연성: CPU의 해시 맵은 충돌 발생 시 연결 리스트를 만드는 체이닝(Chaining) 기법을 주로 쓴다. 그러나 GPU 메모리에서 연결 리스트를 따라가는 것(Pointer chasing)은 메모리 접근의 비연속성을 초래하여 성능을 끔찍하게 저하시킨다. 따라서 NvBlox는 충돌이 발생하면 해시 테이블 내의 다른 빈 슬롯을 찾아 데이터를 저장하는 개방형 주소 지정 방식을 채택한다.3
선형 탐사(Linear Probing)와 캐시 지역성: 충돌 해결 전략으로, 충돌 위치에서 고정된 보폭(Stride, 보통 1)만큼 이동하며 빈 슬롯을 찾는 선형 탐사를 주로 사용한다. “왜 더 복잡하고 분포가 좋은 이중 해싱(Double Hashing)이나 Cuckoo Hashing을 쓰지 않는가?“라는 의문이 들 수 있다. 그 이유는 메모리 응집성(Coalescing) 때문이다. 선형 탐사는 충돌 시 바로 옆 메모리를 확인하므로, 이 데이터가 이미 L1/L2 캐시에 로드되어 있을 확률이 매우 높다. 반면, 이중 해싱은 메모리의 엉뚱한 곳으로 점프하므로 캐시 미스를 유발한다. GPU에서는 연산 비용보다 메모리 접근 비용(Latency)이 훨씬 크기 때문에, 다소의 클러스터링(Clustering)을 감수하더라도 선형 탐사가 유리하다.12
병렬 삽입과 원자적 연산(Atomic Operations): 매핑 과정에서 수십 개의 카메라 광선(Ray)이 동시에 동일한 블록(아직 생성되지 않은)에 도달할 수 있다. 이때 여러 스레드가 동시에 “이 블록을 내가 만들겠다“고 경합하는 경쟁 상태(Race Condition)가 발생한다. NvBlox는 CUDA의 atomicCAS(Compare-And-Swap) 명령어를 사용하여 이를 제어한다. 해시 테이블 슬롯의 상태를 원자적으로 확인하고, 오직 하나의 스레드만이 성공적으로 키(Key)를 기록하고 메모리를 할당받도록 보장한다. 실패한 스레드들은 다른 스레드가 이미 할당해 둔 블록 포인터를 안전하게 받아와서 데이터 통합 작업을 수행한다.14

1.2.3 메모리 풀(Memory Pool)과 사전 할당 전략

해시 테이블은 단지 ’주소록’일 뿐이다. 실제 8x8x8 복셀 데이터(Payload)는 어디에 저장되는가? NvBlox는 커널 실행 중의 동적 할당(malloc)을 피하기 위해 **블록 메모리 풀(Block Memory Pool)**을 사용한다.15

사전 할당(Pre-allocation): NvBlox 초기화 시, 혹은 맵이 확장될 때 GPU 메모리의 거대한 덩어리(Chunk)를 미리 할당해 둔다. 이를 ’블록 힙(Block Heap)’이라 부른다.
포인터 대신 인덱스 활용: 해시 테이블의 엔트리는 실제 메모리 주소(Raw Pointer)를 저장할 수도 있지만, 많은 경우 메모리 풀 내의 오프셋(Index)을 저장하는 것이 유리하다. 이는 맵 데이터를 직렬화(Serialization)하여 디스크에 저장하거나 호스트로 복사할 때, 메모리 주소 공간이 바뀌더라도 인덱스 값은 유효하기 때문이다(Relocatable).
블록 재활용(Recycling)과 스트리밍: 로봇이 이동하여 특정 블록이 카메라 시야(Frustum)나 관심 영역(ROI)을 벗어나면, NvBlox는 해당 블록을 호스트 메모리(CPU RAM)로 내보내거나(Swap out), 더 이상 필요 없는 경우 메모리 풀로 반환하여 새로운 블록 할당에 재사용한다. 이 과정은 GPU와 CPU 간의 **비동기 스트림(Async Stream)**을 통해 백그라운드에서 수행되므로, 전경(Foreground)의 매핑 성능에 영향을 주지 않는다.5

1.2.4 구조체 배열(AoS) 대 배열 구조체(SoA): 메모리 레이아웃의 미학

블록 내부의 데이터를 메모리에 어떻게 배치하느냐는 GPU 성능 튜닝의 핵심이다.

AoS (Array of Structures): struct Voxel { float dist; float weight; uchar color; }를 배열로 만드는 방식. 객체지향적 관점에서는 자연스럽지만, GPU에서는 비효율적이다. 예를 들어, TSDF 통합 커널은 dist와 weight만 읽고 쓰면 되는데, color 데이터까지 캐시 라인에 딸려 들어와 유효 메모리 대역폭을 낭비하게 된다.17
SoA (Structure of Arrays): struct VoxelBlock { float dists; float weights; uchar colors; }와 같이 속성별로 배열을 분리하는 방식. NvBlox는 성능 최적화를 위해 이 방식을 지향하거나, 하이브리드 형태를 취한다. 워프 내의 스레드 0번부터 31번이 각각 복셀 0번부터 31번의 dist 값에 접근할 때, SoA 구조에서는 이 데이터들이 메모리 상에 완벽하게 연속되어 있으므로, 단 **한 번의 메모리 트랜잭션(Coalesced Access)**으로 32개의 데이터를 모두 가져올 수 있다. 반면 AoS 구조에서는 데이터가 띄엄띄엄(Strided) 존재하여 32번의 트랜잭션이 발생할 수 있으며, 이는 성능을 10분의 1 이하로 떨어뜨리는 주범이다.9

1.2.5 젯슨(Jetson) 아키텍처를 위한 통합 메모리(Unified Memory) 최적화

NVIDIA Jetson과 같은 임베디드 플랫폼에서는 CPU와 GPU가 물리적인 DRAM을 공유한다. NvBlox는 이를 십분 활용하여 제로 카피(Zero-Copy) 전송을 구현한다.20

통합 메모리 아키텍처(UMA): 일반적인 데스크탑 GPU(Discrete GPU)에서는 CPU 메모리에서 GPU 메모리로 데이터를 보내기 위해 PCIe 버스를 타야 하며, 이 대역폭(약 16~32GB/s)이 병목이 된다. 그러나 Jetson에서는 cudaMallocManaged 또는 매핑된 핀드 메모리(Pinned Memory)를 사용하여, 데이터 복사 없이 포인터만 전달함으로써 GPU가 CPU의 데이터를 직접 읽게 할 수 있다.
ROS 2 NITROS와의 결합: NvBlox는 Isaac ROS의 NITROS(NVIDIA Isaac Transport for ROS) 기술을 통해, 카메라 드라이버가 캡처한 이미지를 ROS 메시지로 직렬화/역직렬화하는 오버헤드 없이, GPU 메모리 포인터 그대로 NvBlox 노드에 전달한다. 이로 인해 4K 고해상도 이미지 처리 시에도 CPU 점유율을 거의 소모하지 않고 맵핑 파이프라인을 구동할 수 있다.21

특성	CPU 기반 매핑 (Voxblox)	NvBlox (GPU 기반)
자료구조	해시 맵 + 연결 리스트/트리	개방형 주소 지정 해시 테이블 + 선형 풀
병렬성	스레드 단위 (제한적)	워프/블록 단위 (대규모 병렬)
메모리 접근	무작위 접근 (Random Access)	병합 접근 (Coalesced Access)
충돌 해결	체이닝 (Chaining)	선형 탐사 (Linear Probing)
데이터 레이아웃	AoS (객체 중심)	SoA (데이터 중심)
할당 방식	동적 할당 (`new`/`delete`)	정적 풀 + 인덱싱

결론적으로, 2.1절에서 다룬 NvBlox의 데이터 구조와 메모리 관리 기법은 “GPU는 수천 개의 멍청한 코어가 엄청난 속도로 메모리를 들이마시는 기계“라는 하드웨어의 본질을 꿰뚫어 본 설계다. 희소 복셀 그리드는 데이터의 양을 줄이고, 해시 테이블과 선형 메모리 풀은 데이터의 접근 경로를 단순화하며, SoA 레이아웃은 데이터의 흐름을 원활하게 한다. 이러한 요소들이 유기적으로 결합됨으로써 NvBlox는 기존 CPU 기반 솔루션 대비 177배라는 경이로운 가속 성능을 달성할 수 있었던 것이다.

2. 참고 자료

nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping | Request PDF, https://www.researchgate.net/publication/382991572_nvblox_GPU-Accelerated_Incremental_Signed_Distance_Field_Mapping
Nvblox - NVIDIA Isaac ROS, https://nvidia-isaac-ros.github.io/concepts/scene_reconstruction/nvblox/index.html
(PDF) coVoxSLAM: GPU Accelerated Globally Consistent Dense SLAM - ResearchGate, https://www.researchgate.net/publication/385318409_coVoxSLAM_GPU_Accelerated_Globally_Consistent_Dense_SLAM
nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping - arXiv, https://arxiv.org/html/2311.00626v2
Real-time 3D Reconstruction at Scale using Voxel Hashing - Matthias Niessner, https://niessnerlab.org/papers/2013/4hashing/niessner2013hashing.pdf
Voxel Block Grid - Open3D 0.19.0 documentation, https://www.open3d.org/docs/release/tutorial/t_reconstruction_system/voxel_block_grid.html
Voxel Block Grid — Open3D 0.17.0 documentation, https://www.open3d.org/docs/0.17.0/tutorial/t_reconstruction_system/voxel_block_grid.html
What is the maximum number of blocks I can use? - CUDA Programming and Performance, https://forums.developer.nvidia.com/t/what-is-the-maximum-number-of-blocks-i-can-use/201587
coVoxSLAM: GPU accelerated globally consistent dense SLAM - arXiv, https://arxiv.org/html/2410.21149v1
16x16 VS 32x8 large difference -> bug? - CUDA Programming and Performance, https://forums.developer.nvidia.com/t/16x16-vs-32x8-large-difference-bug/22219
nvblox_ros1/docs/technical-details.md at main - GitHub, https://github.com/ethz-asl/nvblox_ros1/blob/main/docs/technical-details.md
Maximizing Performance with Massively Parallel Hash Maps on GPUs - NVIDIA Developer, https://developer.nvidia.com/blog/maximizing-performance-with-massively-parallel-hash-maps-on-gpus/
An apparent performance bug with some std::map and std::unordered_map implementations : r/programming - Reddit, https://www.reddit.com/r/programming/comments/4wgzem/an_apparent_performance_bug_with_some_stdmap_and/
stdgpu: Efficient STL-like Data Structures on the GPU - GitHub, https://github.com/stotko/stdgpu
Nvblox quickstart example crashing - Isaac ROS - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/nvblox-quickstart-example-crashing/333188
Isaac ROS Nvblox, https://nvidia-isaac-ros.github.io/repositories_and_packages/isaac_ros_nvblox/index.html
Machine Learning Frameworks Interoperability, Part 1: Memory Layouts and Memory Pools | NVIDIA Technical Blog - NVIDIA Developer, https://developer.nvidia.com/blog/machine-learning-frameworks-interoperability-part-1-memory-layouts-and-memory-pools/
Memory coalescing and multiple arrays - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/memory-coalescing-and-multiple-arrays/8206
Coalesced memory access to 2d array with CUDA - Stack Overflow, https://stackoverflow.com/questions/28788728/coalesced-memory-access-to-2d-array-with-cuda
R²D²: Building AI-based 3D Robot Perception and Mapping with NVIDIA Research, https://developer.nvidia.com/blog/r2d2-building-ai-based-3d-robot-perception-and-mapping-with-nvidia-research/
NITROS - NVIDIA Isaac ROS, https://nvidia-isaac-ros.github.io/concepts/nitros/index.html